#include "main/utils.h"
#include "lib/binary_tree.h"
using namespace std;

using TreeNode = BinaryTreeNode;

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
      if (!root)
        return {};
      vector<int> ret;
      auto left_ret = inorderTraversal(root->left);
      ret.insert(ret.end(), left_ret.begin(), left_ret.end());
      ret.push_back(root->value);
      auto right_ret = inorderTraversal(root->right);
      ret.insert(ret.end(), right_ret.begin(), right_ret.end());
      return ret;
    }

    vector<int> inorderTraversal1(TreeNode* root) {
      stack<TreeNode*> stack;
      TreeNode* cur = root;
      vector<int> ret;
      while (cur || !stack.empty()) {
        while (cur) {
          stack.push(cur);
          cur = cur->left;
        }
        cur = stack.top();
        stack.pop();
        ret.push_back(cur->value);
        cur = cur->right;
      }
      return ret;
    }
};

int main() {
  vector<int> nums = {1, 2, 3, 4, 5, 6, 7};
  auto root = CreateBinaryTree(nums);

  Solution su;
  auto ret = su.inorderTraversal(root);
  printVec("leetcode94", ret);

  auto ret1 = su.inorderTraversal1(root);
  printVec("leetcode94", ret1);

  return 0;
}
